# -*- coding: utf-8 -*-
# Created by zhangyanqi on 2018/4/27

"""
对称二叉树
给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3
说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

思路：
    中序遍历和层序遍历的结果对称
"""


# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x, l, r):
        self.val = x
        self.left = l
        self.right = r


class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        r = root
        """
        中序遍历判断
        """
        result = []
        l = []
        while len(l) > 0 or root is not None:
            if root is not None:
                l.append(root)
                root = root.left
            else:
                pop = l.pop(len(l) - 1)
                result.append(pop.val)
                root = pop.right
        for i in range(int(len(result) / 2)):
            if result[i] != result[len(result) - i - 1]:
                return False

        """
        层序遍历判断
        """
        # 每层的内容
        temp = []
        # 每层总数
        count = 0
        # 层
        tier = 1
        l = [r]
        while len(l) != 0:
            # 取出
            root = l.pop(0)
            count += 1
            # 判断队列中是否全部都是none，如果是,将上一层的结果放入结果集中，终止
            if root is None:
                is_all_none = True
                for i in l:
                    if i is not None:
                        is_all_none = False
                        break
                if is_all_none:
                    if len(temp) != 0:
                        for i in range(int(len(temp) / 2)):
                            if temp[i] != temp[len(temp) - 1 - i]:
                                return False
                    return True
                l.append(None)
                l.append(None)
                if count == 2 ** (tier - 1):
                    for i in range(int(len(temp) / 2)):
                        if temp[i] != temp[len(temp) - 1 - i]:
                            return False
                    temp = []
                    tier += 1
                    count = 0
                continue
            temp.append(root.val)
            if count == 2 ** (tier - 1):
                for i in range(int(len(temp) / 2)):
                    if temp[i] != temp[len(temp) - 1 - i]:
                        return False
                temp = []
                tier += 1
                count = 0
            if root.left is not None:
                l.append(root.left)
            else:
                l.append(None)
            if root.right is not None:
                l.append(root.right)
            else:
                l.append(None)
        return True


if __name__ == "__main__":
    node6 = TreeNode(2, None, None)
    node5 = TreeNode(3, None, None)
    node4 = TreeNode(3, None, None)
    node3 = TreeNode(3, node6, None)
    node2 = TreeNode(2, node4, None)
    node1 = TreeNode(1, node2, node3)
    s = Solution()
    symmetric = s.isSymmetric(node1)
    print(symmetric)
